/*
 *  完全背包模板 整数拆分
 * */

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 21, M = 1000010, MOD = 1e9;
int m;
int f[M];

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m;

    f[0] = 1;
    for (int i = 1; i <= m; i *= 2) {
        for (int j = i; j <= m; ++j) {
            f[j] = (f[j] + f[j - i]) % MOD;
        }
    }

    cout << f[m] << endl;

    return 0;
}